#include "BTreeNode.h"
#include <iostream>
using namespace std;

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */

BTLeafNode::BTLeafNode()
{
	memset(buffer, 0, PageFile::PAGE_SIZE);
}


RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	memset(buffer, 0, PageFile::PAGE_SIZE);
	return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	return pf.write(pid, buffer); 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	int size = 0;
	memcpy(&size, &buffer, sizeof(int));
	//first four bytes in the page is used to store # records in the page.
	return size;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	int slotsize = sizeof(RecordId) + sizeof(int);
	int totalsize = getKeyCount() * slotsize;
	int pagesize=PageFile::PAGE_SIZE;

	if(totalsize + slotsize >= pagesize) 
	{
		cout << "Non-leaf Node is full" << endl;
		return RC_NODE_FULL;
	}

	char* currpos = &(buffer[0]);
	int i = 0;

	currpos += sizeof(int) + sizeof(PageId);

	int currKey;
	while (currpos) {
		memcpy(&currKey, currpos, sizeof(int));
		if(currKey == 0) 
		{
			break;
		}
		if (currKey < key) 
		{
			currpos += slotsize;
			i++;
		} 
		else 
		{
			break;
		}
	}

	if (&(buffer[pagesize]) - currpos < 20) {
		cout << "Node is full" << endl;
		return RC_NODE_FULL;
	}

	char* tempbuf = (char*) malloc(pagesize * sizeof(char));
	memset(tempbuf, 0, pagesize);
	if(totalsize > 0 && currKey != 0) {
		memcpy(tempbuf, currpos, totalsize - (slotsize * i));
		memset(tempbuf, 0, totalsize - (slotsize * i));
	}

	memcpy(currpos, &key, sizeof(int)); 
	currpos += sizeof(int);
	memcpy(currpos, &rid, sizeof(RecordId));

	currpos += sizeof(RecordId);
	if(totalsize > 0 && currKey != 0) 
	{
		memcpy(currpos, tempbuf, totalsize - (slotsize * i));
	}
	free(tempbuf);

	//set the new key count
	int currCount = getKeyCount();
	currCount++;
	currpos = &(buffer[0]);
	memcpy(currpos, &currCount, sizeof(int));
	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	int slotsize = sizeof(RecordId) + sizeof(int);
	int totalsize = getKeyCount() * slotsize;
	int oldsize = getKeyCount() / 2;
	int pagesize= PageFile::PAGE_SIZE;
	char* currpos = &(buffer[0]);
	currpos += sizeof(int) + sizeof(PageId);

	for(int i=0; i<oldsize ;i++)
		currpos += slotsize;

	char* tempbuf = (char*) malloc(pagesize * sizeof(char));
	char* temphead = tempbuf;
	//move right part of newnode to tempbuf
	memset(tempbuf, 0, pagesize*sizeof(char));
	memcpy(tempbuf, currpos, totalsize - (slotsize * oldsize));



	//delete right part from oldnode
	memset(currpos, 0, totalsize - (slotsize * oldsize));
	int newcount = oldsize;
	memcpy(buffer, &newcount, sizeof(int));

	// insert right part to new node
	while(tempbuf) 
	{
		int newkey;
		RecordId newrid;
		memcpy(&newkey, tempbuf, sizeof(int));
		if(newkey == 0) 
			break;
		tempbuf += sizeof(int);
		memcpy(&newrid, tempbuf, sizeof(RecordId));
		tempbuf += sizeof(RecordId);
		if( sibling.insert(newkey, newrid) != 0 ) 
		{
			free(temphead);
			return RC_FILE_WRITE_FAILED;
		}
	}
	free(temphead);

	//store first key in new node
	RecordId newr;
	if( sibling.readEntry(0, siblingKey, newr) != 0) {
		return RC_FILE_READ_FAILED;
	}

	//insert new key 
	if(key < siblingKey && insert(key, rid) != 0) 
			return RC_FILE_WRITE_FAILED;
	else if( sibling.insert(key, rid) != 0 ) 
			return RC_FILE_WRITE_FAILED;

	if( sibling.readEntry(0, siblingKey, newr) != 0) 
		return RC_FILE_READ_FAILED;

	return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
	int slotsize = sizeof(RecordId) + sizeof(int);
	int totalsize = getKeyCount() * slotsize;
	char* currpos = &(buffer[0]);
	int currkey;
	int i = 0;

	currpos += sizeof(int)+sizeof(RecordId);
	while(currpos) 
	{
		memcpy(&currkey, currpos, sizeof(int));
		if(currkey >= searchKey || currkey == 0) 
		{
			eid = i;
			return 0; 
		}
		i++;
		currpos += slotsize;
	}

	return 0;  
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	int slotsize = sizeof(RecordId) + sizeof(int);
	int totalsize = getKeyCount() * slotsize;
	char* currpos = &(buffer[0]);
	int i = 0;

	currpos += sizeof(int) + sizeof(PageId);
	while(currpos && i < eid) 
	{
		currpos += slotsize;
		i++;
	}
	memcpy(&key, currpos, sizeof(int));
	currpos += sizeof(int);
	memcpy(&rid, currpos, sizeof(RecordId));

	return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	PageId pid;
	char* currpos = &(buffer[0]);
	currpos += sizeof(int);
	memcpy(&pid, currpos, sizeof(PageId));
	return pid;  
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	char* currpos = &(buffer[0]);
	currpos += sizeof(int);
	memcpy(currpos, &pid, sizeof(PageId));
	return 0; 
}














BTNonLeafNode::BTNonLeafNode() 
{
	memset(buffer,0,PageFile::PAGE_SIZE);
}
/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
	return pf.read(pid, buffer);  
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	return pf.write(pid, buffer); 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	int size = 0;
	//first four bytes in the page is used to store # records in the page.
	memcpy(&size, &buffer, sizeof(int));
	return size;
}

RC BTNonLeafNode::readEntry(int eid, int& key) 
{
	int slotsize = sizeof(PageId) + sizeof(int);
	int totalsize = getKeyCount() * slotsize;
	int i = 0;

	char* currpos = &(buffer[0]) + sizeof(int);
	
	while(currpos) 
	{
		currpos += sizeof(PageId);
		if(i == eid) {
			memcpy(&key, currpos, sizeof(int));
			return 0;
		}
		currpos += slotsize;
	}

	return 0;
}
/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	int slotsize = sizeof(PageId) + sizeof(int);
	int totalsize = getKeyCount() * slotsize;
	char* currpos = &(buffer[0]);
	int i = 0;
	int pagesize=PageFile::PAGE_SIZE;


	// check if there is enough room
	if(totalsize + slotsize >= pagesize) 
	{
		cout << "Non-leaf Node is full" << endl;
		return RC_NODE_FULL;
	}

	//jump to the first key
	currpos += sizeof(int) + sizeof(PageId);

	int currKey;
	while (currpos) {
		memcpy(&currKey, currpos, sizeof(int));
		if(currKey == 0)  // empty room
		{
			break;
		}
		if (currKey < key)  // not big enough
		{
			currpos += slotsize;
			i++;
		} else {   // have to insert in between or update
			break;
		}
	}

	if(currKey == key)  // need to update
	{
		cout << "Updating this key" << endl;
		currpos += sizeof(int);
		memcpy(currpos, &pid, sizeof(PageId));
		return 0;
	}

	// prepare the temp buffer for inserting a value in between 
	char* tempbuf = (char*) malloc(pagesize * sizeof(char));
	memset(tempbuf, 0, pagesize);


	if(totalsize < 0 && currKey < 0) 
	{
		cout <<"Failed to insert this key!" <<endl;
		return RC_FILE_WRITE_FAILED;
	}

	memcpy(tempbuf, currpos, totalsize - (slotsize * i));
	memset(currpos, 0, totalsize - (slotsize * i));
	
	//insert the new key
	memcpy(currpos, &key, sizeof(int));
	currpos += sizeof(int);
	memcpy(currpos, &pid, sizeof(PageId));
	currpos += sizeof(PageId);


	if(totalsize < 0 && currKey < 0) 
	{
		cout <<"Failed to insert this key!" <<endl;
		return RC_FILE_WRITE_FAILED;
	}

	// copy back the old key
	memcpy(currpos, tempbuf, totalsize - (slotsize * i));
	free(tempbuf);

	//set the new key count
	int currCount = getKeyCount();
	currCount++;
	currpos = &(buffer[0]);
	memcpy(currpos, &currCount, sizeof(int));

	return 0; 
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	
	int slotsize = sizeof(PageId) + sizeof(int);
	int totalsize = getKeyCount() * slotsize;
	int pagesize=PageFile::PAGE_SIZE;
	int oldsize=getKeyCount()/2;
	int newsize=getKeyCount()-oldsize;

	char* currpos = &(buffer[0]);
	//jump to first slot
	currpos += sizeof(int);


	for(int i=0; i<oldsize ;i++)
		currpos += slotsize;


	char* tempbuf = (char*) malloc(pagesize * sizeof(char));
	char* temphead = tempbuf;
	//move the right part of old node to tempbuf
	memset(tempbuf, 0, pagesize*sizeof(char));
	memcpy(tempbuf, currpos, totalsize - (slotsize * oldsize));

	//set the new number of keys in old page
	memset(currpos, 0, totalsize - (slotsize * oldsize));
	int newcount = oldsize;
	memcpy(buffer, &newcount, sizeof(int));

    memcpy(&midKey,tempbuf,sizeof(int));

	while(tempbuf) 
	{
		int newkey;
		PageId newpid;
		memcpy(&newkey, tempbuf, sizeof(int));
		if(newkey == 0) 
			break;
		tempbuf += sizeof(int);
		memcpy(&newpid, tempbuf, sizeof(PageId));
		tempbuf += sizeof(PageId);
		if( sibling.insert(newkey, newpid) != 0) 
		{
			free(temphead);
			return RC_FILE_WRITE_FAILED;
		}
	}
	free(temphead);

	if( sibling.readEntry(0, midKey) != 0 ) 
		return RC_FILE_READ_FAILED;

	//insert the new key
	if( key < midKey && insert(key, pid) != 0 )
			return RC_FILE_WRITE_FAILED;
	else if( sibling.insert(key, pid) != 0 ) 
			return RC_FILE_WRITE_FAILED;

	return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
	//@done
	//seek to search key
	//memcpy out the pid

	int slotsize = sizeof(PageId) + sizeof(int);
	int totalsize = getKeyCount() * slotsize;
	char* currpos = &(buffer[0]);
	int currkey;

	currpos += sizeof(int);
	currpos += sizeof(PageId);

	while(currpos) 
	{
		memcpy(&currkey,currpos , sizeof(int));
		if(currkey != 0 && currkey < searchKey) 
		{
			currpos += slotsize;
			
		} 
		else 
		{
			currpos -= sizeof(PageId);
			memcpy(&pid, currpos, sizeof(PageId));
			return 0;	
		}
	}
 
	return 0;	
	
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
	int keynum = 1;
	size_t soi=sizeof(int);
	char* content = &(buffer[0]);

	memcpy(buffer, &keynum, soi);
	//first place is # of records

	content += soi;
	memcpy(content, &pid1, sizeof(PageId));
	//second place is pid1

	content += soi;
	memcpy(content, &key, soi);
	//third place is the key

	content += soi;
	memcpy(content, &pid2, sizeof(PageId));
	//fourth place is pid2


	return 0; 
}
